import java.util.Scanner;


public class Test {
    public static MySingleList.ListNode mergeTwoLists
            (MySingleList.ListNode head1, MySingleList.ListNode head2) {
        MySingleList.ListNode newHead = new MySingleList.ListNode(0);
        MySingleList.ListNode tmp = newHead;

        while (head1 != null && head2 != null) {
            if(head1.val < head2.val) {
                tmp.next = head1;
                head1 = head1.next;
            }else {
                tmp.next = head2;
                head2 = head2.next;
            }
            tmp = tmp.next;
        }
        if(head1 != null) {
            tmp.next = head1;
        }
        if(head2 != null) {
            tmp.next = head2;
        }
        return newHead.next;
    }


    public static void main(String[] args) {
        MySingleList mySingleList = new MySingleList();
        mySingleList.addLast(11);
        mySingleList.addLast(21);
        mySingleList.addLast(31);
        mySingleList.addLast(41);
        mySingleList.display();


        MySingleList mySingleList2 = new MySingleList();
        mySingleList2.addLast(8);
        mySingleList2.addLast(15);
        mySingleList2.addLast(25);
        mySingleList2.addLast(30);
        mySingleList2.display();

        System.out.println("===============");
        MySingleList.ListNode ret =
                mergeTwoLists(mySingleList.head,mySingleList2.head);
        mySingleList2.display(ret);
    }



    public static void main3(String[] args) {
        MySingleList mySingleList = new MySingleList();
        System.out.println("====测试插入===");
        mySingleList.addLast(1);
        mySingleList.addLast(2);
        mySingleList.addLast(3);
        mySingleList.addLast(4);
        mySingleList.display();
        System.out.println("=========");
        /*MySingleList.ListNode ret = mySingleList.reverseList();
        mySingleList.display(ret.next);*/
        MySingleList.ListNode ret = mySingleList.findKthToTail(5);
        System.out.println(ret.val);
    }
    public static void main2(String[] args) {
        MySingleList mySingleList = new MySingleList();
        //mySingleList.createLink();
        mySingleList.display();
        System.out.println("=======");
        System.out.println(mySingleList.contains(90));
        System.out.println(mySingleList.size());
        System.out.println("====测试插入===");
        mySingleList.addLast(1);
        mySingleList.addLast(1);
        mySingleList.addLast(1);
        mySingleList.addLast(1);
        try {
            mySingleList.addIndex(0,1);
        }catch (ListIndexOutOfException e) {
            e.printStackTrace();
        }
        mySingleList.display();
        System.out.println("=============");
        mySingleList.removeAllKey(1);
        mySingleList.display();
    }


    public void merge(int A[], int m, int B[], int n) {
        int i = m-1;
        int j = n-1;
        int k = m+n-1;
        // 两个数组当中  都有数据
        while (i >= 0 && j >= 0) {
            if(A[i] <= B[j]) {
                A[k] = B[j];
                j--;
                k--;
            }else {
                A[k] = A[i];
                k--;
                i--;
            }
        }
        //有可能A走完了 但是B里面仍然有数据
        while (j >= 0) {
            A[k] = B[j];
            j--;
            k--;
        }
    }

    public static void main1(String[] args) {
        Scanner scan = new Scanner(System.in);
        while(scan.hasNextLine()) {
            String str = scan.nextLine();
            String ret = func(str);
            System.out.println(ret);
        }
    }
    private static String func(String str) {
        boolean[] flg = new boolean[127];//false
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < str.length();i++) {
            char ch = str.charAt(i);
            if(flg[ch] == false) {
                sb.append(ch);
                flg[ch] = true;
            }
        }
        return sb.toString();
    }
}